{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #只出现一次的数字 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: singleNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #只出现一次的数字 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code> ，除某个元素仅出现 <strong>一次</strong> 外，其余每个元素都恰出现 <strong>三次 。</strong>请你找出并返回那个只出现了一次的元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,3,2]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,1,0,1,0,1,100]\n",
    "<strong>输出：</strong>100\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>nums</code> 中，除某个元素仅出现 <strong>一次</strong> 外，其余每个元素都恰出现 <strong>三次</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 137&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/single-number-ii/\">https://leetcode-cn.com/problems/single-number-ii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [WGki4K](https://leetcode.cn/problems/WGki4K/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [WGki4K](https://leetcode.cn/problems/WGki4K/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,2]', '[0,1,0,1,0,1,99]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        #依次计算答案的每个二进制位\n",
    "        ans=0\n",
    "        for i in range(32):\n",
    "            total=sum((num>>i)&1 for num in nums)\n",
    "            if total%3==1: #total=0或3时，都对答案没有贡献\n",
    "                #python需要对最高位单独进行判断\n",
    "                if i==31:\n",
    "                    ans-=(1<<i)\n",
    "                else:\n",
    "                    ans|=(1<<i)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        return (sum(set(nums)) * 3 - sum(nums)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        return (sum(set(nums))*3-sum(nums))//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0 # 结果\n",
    "        for i in range(32):\n",
    "            cnt = 0 # 记录每一位的数量\n",
    "            for num in nums: # 每一位统计所有数字\n",
    "                cnt += ((num >> i) & 1) # 将num右移i位，然后与1\n",
    "            if cnt % 3 != 0:# 如果该位模3不为0，则说明是单独那个数的位置不为1。\n",
    "                if i == 31:\n",
    "                    res -= (1 << i)\n",
    "                else:\n",
    "                    res |= (1 << i) # 结果加上该位为1，也可以写作res |= ((cnt % 3) << i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        once = 0\n",
    "        twice =0\n",
    "        for i in nums:\n",
    "            once = ~twice & (i ^ once)\n",
    "            twice = ~once & (i ^ twice)\n",
    "        return once"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            if total % 3:\n",
    "                # Python 这里对于最高位需要特殊判断\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        for i in range(32):\n",
    "            cnt = 0\n",
    "            for num in nums: # 所有数字二进制求和\n",
    "                cnt += num >> i & 1\n",
    "            if cnt % 3:\n",
    "                if i == 31: #  若为1则表示负数，需要对ret进行减\n",
    "                    ret -= (1 << i)\n",
    "                else:\n",
    "                    ret |= 1 << i\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            if total % 3:\n",
    "                # Python 这里对于最高位需要特殊判断\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            if total % 3:\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for num in nums:\n",
    "            ones = ones ^ num & ~twos\n",
    "            twos = twos ^ num & ~ones\n",
    "        return ones\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        cnt = [0]*32\n",
    "        for x in nums:\n",
    "            for i in range(32):\n",
    "                if (x>>i) & 1:\n",
    "                    cnt[i]+=1\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            if cnt[i]%3:\n",
    "                # 需要注意的是，「有符号整数类型」（即 int 类型）的第 31 个二进制位（即最高位）是补码意义下的符号位，对应着 -2^{31}，\n",
    "                # 而「无符号整数类型」由于没有符号，第 31 个二进制位对应着 2^{31}\n",
    "                if i == 31:\n",
    "                    ans -= (1<<i)\n",
    "                else:\n",
    "                    ans += (1<<i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(32):\n",
    "            total=sum(num>>i & 1 for num in nums)\n",
    "            if total%3:\n",
    "                if i==31:\n",
    "                    ans-=(1<<i)\n",
    "                else:\n",
    "                    ans|=(1<<i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                cnt += num >> i & 1\n",
    "            if cnt % 3:\n",
    "                if i == 31:\n",
    "                    res -= 1 << i\n",
    "                else:\n",
    "                    res |= 1 << i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        flag = False\n",
    "\n",
    "        for i in range(32):\n",
    "            tmp = sum((num >> i) & 1 for num in nums)\n",
    "            if tmp % 3:\n",
    "                if i == 31:\n",
    "                    flag = True\n",
    "                res += 1 << i\n",
    "        \n",
    "        if flag:\n",
    "            res = ~(res ^ 0xffffffff)\n",
    "    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for num in nums:\n",
    "            ones = ones ^ num & ~twos\n",
    "            twos = twos ^ num & ~ones\n",
    "        return ones\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            if total % 3:\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        cnt = [0]*32\n",
    "        for x in nums:\n",
    "            for i in range(32):\n",
    "                cnt[i] += (x>>i)&1\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res=res|((cnt[i]%3)<<i)\n",
    "        if cnt[31]%3==1:\n",
    "            \n",
    "            res=res-2**32\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            if total % 3:\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        a, b = 0, 0\n",
    "        for num in nums:\n",
    "            a, b = (~a & b & num) | (a & ~b & ~num), ~a & (b^num)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            if total % 3:\n",
    "                if i == 31:\n",
    "                    ans -= 1 << i\n",
    "                else:\n",
    "                    ans |= 1 << i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        one, two = 0, 0\n",
    "        for num in nums:\n",
    "            one = one ^ num & ~two\n",
    "            two = two ^ num & ~one\n",
    "        return one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            if total % 3:\n",
    "                # Python 这里对于最高位需要特殊判断\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        a=b=0\n",
    "        for num in nums:\n",
    "            a,b=(~a&b&num)|(a&~b&~num),~a&(b^num)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        flag = 1\n",
    "        for i in range(32):\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if flag & num:\n",
    "                    cnt += 1\n",
    "            \n",
    "            if cnt % 3:\n",
    "                res |= flag\n",
    "            \n",
    "            flag <<= 1\n",
    "        \n",
    "        return res - (1<<32) if res & (1 << 31) else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        for i in nums:\n",
    "            if nums.count(i)==1:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for num in nums:\n",
    "            ones = ones ^ num & ~twos\n",
    "            twos = twos ^ num & ~ones\n",
    "        return ones\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        bit_cnt = [0] * 32\n",
    "\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                if num & (1 << i):\n",
    "                    bit_cnt[i] += 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if bit_cnt[i] % 3:\n",
    "                res = res | (1 << i)\n",
    "        \n",
    "        return res - (1<<32) if res & (1 << 31) else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:return nums[0]\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if i==0 and nums[i]!=nums[i+1]:\n",
    "                return nums[0]\n",
    "            elif i==len(nums)-1 and nums[i]!=nums[i-1]:\n",
    "                return nums[-1]\n",
    "            else:\n",
    "                if nums[i]!=nums[i+1] and nums[i]!=nums[i-1]:\n",
    "                    return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        x = [0 ] * 33\n",
    "        for num in nums:\n",
    "            print(str(bin(num)))\n",
    "            if num > 0:\n",
    "                x[0] += 0\n",
    "                num = str(bin(num))[2:]\n",
    "            else:\n",
    "                x[0] += 1\n",
    "                num = str(bin(num))[3:]\n",
    "            for i in range(len(num)):\n",
    "                i = - i - 1\n",
    "                x[i] += int(num[i])\n",
    "        x = [_ % 3 for _ in x]\n",
    "        print(x)\n",
    "        result = \"\"\n",
    "        for _ in x[1:]:\n",
    "            result += str(_)\n",
    "                \n",
    "        print(result)\n",
    "        result = int(result, 2)\n",
    "        if x[0] == 1:\n",
    "            result *= -1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        # 统计所有数字的二进制表示的每一位上1出现的次数\n",
    "        bits = [0] * 32\n",
    "        for num in nums:\n",
    "            for j in range(32):\n",
    "                bits[j] += num >> j & 1\n",
    "        # 对3取余数，得到只出现一次的数字的二进制表示\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res += (bits[i] % 3) << i\n",
    "        # 将二进制表示转换为整数\n",
    "        return res if res < 2**31 else res - 2**32"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        for i in range(0,len(nums)-1,3):\n",
    "            if nums[i] != nums[i+1]:\n",
    "                return nums[i]\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ret=0\n",
    "        for i in range(32):\n",
    "            n = sum([(num>>i)&1 for num in nums])%3\n",
    "            if i==31:\n",
    "                ret -= (n<<i)\n",
    "            else:\n",
    "                ret+=(n<<i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        for i in range(0,len(nums)-3,3):\n",
    "            if nums[i] == nums[i+1] and nums[i] == nums[i+2]:\n",
    "                continue\n",
    "            else:\n",
    "                return nums[i]\n",
    "        return nums[-1]\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        right = 0\n",
    "\n",
    "        while right < len(nums):\n",
    "            \n",
    "            if right + 1 < len(nums):\n",
    "                if nums[right + 1] != nums[right]:\n",
    "                    return nums[right]\n",
    "\n",
    "            if right + 1 >= len(nums):\n",
    "                return nums[-1]\n",
    "\n",
    "            while right + 1 < len(nums) and nums[right+1] == nums[right]:\n",
    "                right += 1\n",
    "            \n",
    "            right += 1\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            total = sum((num >> i) & 1 for num in nums)\n",
    "            print(total)\n",
    "            if total % 3:\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            d[num] = d.get(num, 0) + 1\n",
    "        for k, v in d.items():\n",
    "            if v == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        # if len(nums)==1:\n",
    "        #     return nums[0]\n",
    "        # #elif len(nums)==2:\n",
    "\n",
    "        # nums.sort()#排毒\n",
    "        # for i in range(len(nums)):\n",
    "        #     if i==0:\n",
    "        #         if nums[i]!=nums[i+1]:\n",
    "        #            return nums[i]\n",
    "        #     elif i ==(len(nums)-1):\n",
    "        #         if nums[i]!=nums[i-1]:\n",
    "        #             return nums[i]\n",
    "        #     elif nums[i]!=nums[i+1] and nums[i]!=nums[i-1]:\n",
    "        #         return nums[i]\n",
    "\n",
    "        #二分法\n",
    "        \n",
    "        #其余元素都是出现3次\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "\n",
    "        nums.sort() #这里就确定了相同的值一定是排列在一起的\n",
    "        loc = 0\n",
    "        while loc<len(nums)-1:\n",
    "            if nums[loc]!=nums[loc+1]:\n",
    "                return nums[loc]\n",
    "            loc = loc + 3\n",
    "                \n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        \n",
    "        if len(nums) == 1 or (nums[1]!=nums[0]):\n",
    "            return nums[0]\n",
    "        if nums[-1] != nums[-2]:\n",
    "            return nums[-1]\n",
    "\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            if nums[i + 1] != nums[i] and nums[i-1] != nums[i]:\n",
    "                return nums[i]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        # stack = [nums[0], nums[1]]\n",
    "        # for n in nums[2:]:\n",
    "        #     if n == stack[-2]: # index error\n",
    "        #         stack.pop(-1)\n",
    "        #         stack.pop(-1)\n",
    "        #     else:\n",
    "        #         stack.append(n)\n",
    "        # return stack[0]\n",
    "        step = 0\n",
    "        while step < len(nums) - 1:\n",
    "            if nums[step] == nums[step+1]:\n",
    "                step += 3\n",
    "            else:\n",
    "                return  nums[step]\n",
    "\n",
    "        return nums[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        label=[]\n",
    "        label2=[]\n",
    "        for i in nums:\n",
    "            if i not in label:\n",
    "                label.append(i)\n",
    "            else:\n",
    "                label2.append(i)\n",
    "        return [k for k in label if k not in label2] [0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            # (num << i) & 1 判断num的第i位是不是1\n",
    "            total = sum([(num >> i) & 1 for num in nums])\n",
    "            # total 不是3的倍数\n",
    "            if total % 3 != 0:\n",
    "                if i == 31:\n",
    "                    ans -= (1 << i)\n",
    "                else:\n",
    "                    ans |= (1 << i)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        \n",
    "        nums.sort()\n",
    "        \n",
    "        if len(nums) == 1 or nums[0] != nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[-2] != nums[-1]:\n",
    "            return nums[-1]\n",
    "\n",
    "        for i in range(1, len(nums) - 1):\n",
    "\n",
    "            if nums[i] == nums[i - 1] or nums[i] == nums[i + 1]:\n",
    "                continue\n",
    "            else:\n",
    "                return nums[i]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        # list1 = list(range(len(nums)))\n",
    "        nums.sort()\n",
    "        for i in range(0,len(nums),3):\n",
    "            try:\n",
    "                if(nums[i] != nums[i+2]):return nums[i]\n",
    "            except:\n",
    "                return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        # 常规用字典统计\n",
    "        from collections import defaultdict\n",
    "        hash_map = defaultdict(int)\n",
    "        for i in nums:\n",
    "            hash_map[i] += 1\n",
    "        for key, value in hash_map.items():\n",
    "            if value == 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        neg_cnt = sum([1 if i < 0 else 0 for i in nums])\n",
    "        neg = neg_cnt % 3 == 1\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            cnt = 0\n",
    "            for n in nums:\n",
    "                if neg and n >= 0 or not neg and n < 0:\n",
    "                    continue\n",
    "                if neg:\n",
    "                    n = -n\n",
    "                if 1 << i & n:\n",
    "                    cnt+=1\n",
    "            if cnt % 3 == 1:\n",
    "                res |= 1 << i \n",
    "        return res if not neg else -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        freq = collections.Counter(nums)\n",
    "        ans = [num for num, occ in freq.items() if occ == 1][0]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        mapper = {}\n",
    "        for item in nums:\n",
    "            if item not in mapper.keys():\n",
    "                mapper[item] = 1\n",
    "            else:\n",
    "                mapper[item] += 1\n",
    "        for num, cnt in mapper.items():\n",
    "            if cnt == 1:\n",
    "                return num\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        cnt = collections.Counter(nums)\n",
    "        ans = [num for num, occ in cnt.items() if occ == 1]\n",
    "\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        num_dict = defaultdict(int)\n",
    "        for num in nums:\n",
    "            num_dict[num] += 1\n",
    "        \n",
    "        for k in num_dict:\n",
    "            if num_dict[k]==1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        fre = collections.Counter(nums)\n",
    "        ans = [num for num,i in fre.items() if i == 1][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        cnt_map = {}\n",
    "        for n in nums:\n",
    "            if n not in cnt_map:\n",
    "                cnt_map[n] = 0\n",
    "            cnt_map[n] += 1\n",
    "        for k in cnt_map.keys():\n",
    "            if cnt_map[k] == 1:\n",
    "                return k\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        numsdict = {}\n",
    "        for i in nums:\n",
    "            if i in numsdict:\n",
    "                numsdict[i] += 1\n",
    "                if numsdict[i] == 3:\n",
    "                    del numsdict[i]\n",
    "            else:\n",
    "                numsdict[i] = 1\n",
    "        key = list(numsdict.keys())\n",
    "        return key[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        for num in nums:\n",
    "            d[num] += 1\n",
    "        \n",
    "        for key,val in d.items():\n",
    "            if val == 1:\n",
    "                return key\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        a={}\n",
    "        for i in nums:\n",
    "            a[i]=i not in a\n",
    "        for i in a:\n",
    "            if a[i]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        for k ,v in dic.items():\n",
    "            if v == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dic = collections.Counter(nums)\n",
    "        \n",
    "        for i in nums:\n",
    "            if dic[i]==1:\n",
    "                return i \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        \n",
    "        for i in nums:\n",
    "            if dic[i]==1:\n",
    "                return i \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i not in dic.keys():\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        for key,value in dic.items():\n",
    "            if value == 1:\n",
    "                return key\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        number = Counter(nums)\n",
    "        for key in number:\n",
    "            if number[key] == 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            if num not in dic:\n",
    "                dic[num] = 1\n",
    "            else:\n",
    "                dic[num] += 1\n",
    "        for key in dic:\n",
    "            if dic[key] == 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        res = defaultdict(int)\n",
    "        for num in nums:\n",
    "            res[num] += 1\n",
    "        \n",
    "        for k, v in res.items():\n",
    "            if res[k] == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        vis = defaultdict(int)\n",
    "        for num in nums:\n",
    "            vis[num] += 1\n",
    "        for k, v in vis.items():\n",
    "            if v == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        res = {}\n",
    "        for num in nums:\n",
    "            res[num] = res.get(num, 0) + 1\n",
    "        \n",
    "        for i in res.keys():\n",
    "            if res[i] == 1:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        myset = set()\n",
    "        for num in nums:\n",
    "            myset.add(num)\n",
    "        sum1 = sum(myset)\n",
    "        sum2 = sum(nums)\n",
    "        return (sum1*3-sum2) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        distinct_nums = set(nums)\n",
    "        sum_of_distinct_nums = sum(distinct_nums)\n",
    "        sum_of_nums = sum(nums)\n",
    "        # 所有不重复的数的和*3-当前和=2*出现三次的数\n",
    "        tgt_num = (sum_of_distinct_nums*3-sum_of_nums)//2\n",
    "        return tgt_num\n",
    "\n",
    "\n",
    "        \n",
    "        # num_dict = defaultdict(int)\n",
    "        # for num in nums:\n",
    "        #     num_dict[num] += 1\n",
    "        \n",
    "        # for k in num_dict:\n",
    "        #     if num_dict[k]==1:\n",
    "        #         return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        memo=Counter(nums)\n",
    "        for k,v in memo.items():\n",
    "            if v==1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - (sum(nums) - sum(set(nums))) * 3 // 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        return list(sorted([x for x in Counter(nums).items()],key = lambda x:x[1]))[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        nums_dict = {}\n",
    "        for i in nums:\n",
    "            if i not in nums_dict:\n",
    "                nums_dict[i] = 1\n",
    "            else:\n",
    "                nums_dict[i] += 1\n",
    "        for key, value in nums_dict.items():\n",
    "            if value == 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for num in nums:\n",
    "            dic[num] += 1\n",
    "        for k, v in dic.items():\n",
    "            if v == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        dicts = {}\n",
    "        for num in nums:\n",
    "            if num not in dicts:\n",
    "                dicts[num] = 1\n",
    "            else:\n",
    "                dicts[num] += 1\n",
    "        for num, count_ in dicts.items():\n",
    "            if count_==1:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        for x in nums:\n",
    "            d[x] += 1\n",
    "        for k in d:\n",
    "            if d[k] == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        num_set = set(nums)\n",
    "        return (sum(num_set)*3 - sum(nums)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: list[int]) -> int:\n",
    "        result = {}\n",
    "        for i in nums:\n",
    "            if i in result.keys():\n",
    "                result[i] += 1\n",
    "                if result[i] == 3:\n",
    "                    print(result[i])\n",
    "                    del result[i]\n",
    "            else:\n",
    "                result[i] = 1\n",
    "        for i in result.keys():\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        return [i for i in Counter(nums) if Counter(nums)[i]==1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        for i in set(nums):\n",
    "            if nums.count(i) == 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        numset = set()\n",
    "        ressum = 0\n",
    "        setsum = 0\n",
    "        for num in nums:\n",
    "            ressum += num \n",
    "            if(num not in numset):\n",
    "                setsum += num\n",
    "                numset.add(num)\n",
    "        return (setsum*3-ressum)//2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        # numsdict = Counter(nums)\n",
    "        # for k,v in numsdict.items():\n",
    "        #     if v == 1:\n",
    "        #         return k\n",
    "        nums2 = set(nums)\n",
    "        return (sum(nums2) * 3 - sum(nums)) // 2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
